package com.zhang.study.chapter06;

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 最大线段重合问题
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须 >0
 * 返回线段最多重合区域中，包含了几条线段
 */
public class Code04_ConvertMax {

    public static int getMaxConvert01(int[][] segments) {
        if (segments == null || segments.length == 0) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] segment : segments) {
            min = Math.min(min, segment[0]);
            max = Math.max(max, segment[1]);
        }
        int ans = 0;
        for (double i = min + 0.5; i < max; i++) {
            int cur = 0;
            for (int[] segment : segments) {
                if (segment[0] < i && segment[1] > i) {
                    cur++;
                }
            }
            ans = Math.max(ans, cur);
        }
        return ans;
    }
    public static int getMaxConvert02(int[][] segments) {
        if (segments == null || segments.length == 0) {
            return 0;
        }
        Arrays.sort(segments, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int ans = 0;

        for (int[] segment : segments) {
            while (!heap.isEmpty() && heap.peek() <= segment[0]) {
                heap.poll();
            }
            heap.add(segment[1]);
            ans = Math.max(ans, heap.size());
        }
        return ans;
    }

    public static int[][] generateLines(int N, int L, int R) {
        int size = (int) (Math.random() * N) + 1;
        int[][] ans = new int[size][2];
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) {
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println("test begin");
        int N = 100;
        int L = 0;
        int R = 200;
        int testTimes = 200000;
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(N, L, R);
            int ans1 = getMaxConvert01(lines);
            int ans2 = getMaxConvert02(lines);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test end");
    }

    public static class Main{
        private static Integer MAX = 10001;

        private static int[][] line = new int[MAX][2];

        private static int n;

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StreamTokenizer in = new StreamTokenizer(br);
            PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
            while (in.nextToken()!=StreamTokenizer.TT_EOF){
                n = (int)in.nval;
                for (int i = 0; i < n; i++) {
                    in.nextToken();
                    line[i][0] = (int)in.nval;
                    in.nextToken();
                    line[i][1] = (int)in.nval;
                }
            }
            out.println(getMaxConvert02());
            out.flush();
            br.close();
        }

        public static int getMaxConvert02() {
            if (line == null || line.length == 0) {
                return 0;
            }
            Arrays.sort(line, Comparator.comparingInt(o -> o[0]));
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            int ans = 0;

            for (int[] segment : line) {
                while (!heap.isEmpty() && heap.peek() <= segment[0]) {
                    heap.poll();
                }
                heap.add(segment[1]);
                ans = Math.max(ans, heap.size());
            }
            return ans;
        }
    }
}
